"""
1137. 第 N 个泰波那契数
https://leetcode.cn/problems/n-th-tribonacci-number/description/?envType=study-plan-v2&envId=dynamic-programming
泰波那契序列 Tn 定义如下： 
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
"""
class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        if n < 3:
            return 1
        T0 = 0 
        T1 = 1 
        T2 = 1
        r = 2
        for i in range(4,n+1):
            T0 = T1
            T1 = T2
            T2 = r
            r = T0 + T1 + T2
        return r


print(Solution().tribonacci(4)) # 4
print(Solution().tribonacci(25)) # 1389537